//
// Created by Administrator on 2021/5/29.
//
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> getAllElements(TreeNode *root1, TreeNode *root2) {
        vector<int> v1;
        vector<int> v2;
        dfs(v1, root1);
        dfs(v2, root2);
        // v1 v2 是有序的
        int m = (int) v1.size();
        int n = (int) v2.size();
        int i = 0, j = 0;
        vector<int> ans;
        while (i < m and j < n) {
            if (v1[i] <= v2[j]) {
                ans.push_back(v1[i++]);
            } else {
                ans.push_back(v2[j++]);
            }
        }
        if (i < m)ans.insert(ans.end(), v1.begin() + i, v1.end());
        if (j < n) ans.insert(ans.end(), v2.begin() + j, v2.end());
        return ans;
    }

    void dfs(vector<int> &v, TreeNode *root) {
        if (root == nullptr) return;
        dfs(v, root->left);
        v.push_back(root->val);
        dfs(v, root->right);
    }

};

class Solution2 {
public:
    vector<int> getAllElements(TreeNode *root1, TreeNode *root2) {
        vector<int> v;
        dfs(v, root1);
        dfs(v, root2);
        sort(v.begin(), v.end());
        return v;
    }

    void dfs(vector<int> &v, TreeNode *root) {
        if (root == nullptr) return;
        dfs(v, root->left);
        v.push_back(root->val);
        dfs(v, root->right);
    }

};

class Solution3 {
public:
    void dfs(TreeNode *node, vector<int> &v) {
        if (!node) {
            return;
        }
        dfs(node->left, v);
        v.push_back(node->val);
        dfs(node->right, v);
    }

    vector<int> getAllElements(TreeNode *root1, TreeNode *root2) {
        vector<int> v1, v2;
        dfs(root1, v1);
        dfs(root2, v2);

        vector<int> ans;
        int i = 0, j = 0;
        while (i < v1.size() || j < v2.size()) {
            if (i < v1.size() && (j == v2.size() || v1[i] <= v2[j])) {
                ans.push_back(v1[i++]);
            } else {
                ans.push_back(v2[j++]);
            }
        }
        return ans;
    }
};


int main() {
    auto n1 = TreeNode(2), n2 = TreeNode(1), n3 = TreeNode(4),
            t1 = TreeNode(1), t2 = TreeNode(0), t3 = TreeNode(3);
    n1.left = &n2;
    n1.right = &n3;
    t1.left = &t2;
    t1.right = &t3;
    Solution2 sol;
    auto ans = sol.getAllElements(&n1, &t1);
    for (auto &x:ans) cout << x << endl;
    return 0;
}